The present invention concerns the use of adaptable topologies in the routing of ground and power networks on an integrated circuit. The invention can also be used in the placement of other special networks such as those used to connect networks which provide a clock signal to component blocks within the integrated circuit.
Once the logic circuitry for a very large scale integrated (VLSI) circuit has been designed, placement algorithms are used to place the VLSI circuit logic efficiently upon a chip. The integrated circuit is generally divided into component blocks of logic circuits. The logic circuits are often referred to as logic cells. Each of the component blocks occupies a fixed area when placed on the chip. Each component block is connected to other component blocks through wire networks, also called connection networks. The connection networks include connection networks which supply a power signal and a ground signal to each of the component blocks. Connection networks which supply a power signal may be referred to as a power line network. Connection networks which supply a ground signal may be referred to as a ground line network.
Connection networks have a measurable width and take up space on the integrated circuit which is directly proportional to their length. Therefore, when routing connection networks between component blocks, it is desirable to find a routing path which minimizes the total length of the connection networks.
For examples of the routing of power line networks and ground line networks in the prior art, see for example, Andrew Strout Moulton, Routing the Power and Ground Wires on a VLSI Chip, a Masters Thesis for the Massachusetts Institute of Technology, MIT/LCS/TR-322, May, 1984. See also Xiao-Ming Xiong and Ernest S. Kuh, The Scan Line Approach to Power and Ground Routing, IEEE, 1986; S. Chowdhury, An Automated Design of Minimum-Area IC Power/Ground Nets, 24th/ACM/IEEE Design Automation Conference, 1987; and Shinichiro Haruyama and Don Fussell, A New Area-Efficient Power Routing Alcorithm for VLSI Layout, IEEE, 1987.
The routing of power line networks and ground line networks on an integrated circuit is more idiosyncratic that normal routing. Depending on the particular circuit and technology being used, there can be constraints on the maximum number of pins connected to a single source, or the amount of overlap allowed between power and ground routing. In addition, a circuit designer may need a particular topology such as power and ground rings to shield the integrated circuit, or such as ladder routing to connect power or ground routing to a pad ring. Such topologies cannot be generated with a generic router, and therefore, special case routers are usually constructed. In situations where the special routers are inadequate or cannot be constructed in time, the circuit designer must manually route the power and ground line networks. However, such manual routing can be extremely complicated as, in a typical case, power and networks may have hundreds of connections.